package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150">在排序数组中查找元素的第一个和最后一个位置(Find First and Last Position of Element in Sorted Array)</a>
 * <p>给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。</p>
 * <p>如果数组中不存在目标值 target，返回 [-1, -1]。</p>
 * <p>你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [5,7,7,8,8,10], target = 8
 *      输出：[3,4]
 *
 * 示例 2：
 *      输入：nums = [5,7,7,8,8,10], target = 6
 *      输出：[-1,-1]
 *
 * 示例 3：
 *      输入：nums = [], target = 0
 *      输出：[-1,-1]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>0 <= nums.length <= 10^5</li>
 *      <li>-10^9 <= nums[i] <= 10^9</li>
 *      <li>nums 是一个非递减数组</li>
 *      <li>-10^9 <= target <= 10^9</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/19 15:13
 */
public class LC0034FindFirstAndLastPositionOfElementInSortedArray_M {
    static class Solution {
        public int[] searchRange(int[] nums, int target) {
            if (nums == null || nums.length == 0) {
                return new int[]{-1, -1};
            }
            int left = 0;
            int right = nums.length - 1;
            int mid;
            while (left <= right) {
                mid = left + ((right - left) >> 1);
                if (nums[mid] > target) {
                    right = mid - 1;
                } else if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    while (left >= 0 && nums[mid] == nums[left]) {
                        --left;
                    }
                    while (right <= nums.length - 1 && nums[mid] == nums[right]) {
                        ++right;
                    }
                    return new int[]{left + 1, right - 1};
                }
            }
            return new int[]{-1, -1};
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        //for (int i : solution.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8)) {
        //    System.out.print(i + "  ");
        //}
        //System.out.println();

        for (int i : solution.searchRange(new int[]{1,1,2}, 1)) {
            System.out.print(i + "  ");
        }
        System.out.println();
        //
        //for (int i : solution.searchRange(new int[]{}, 0)) {
        //    System.out.print(i + "  ");
        //}
        //System.out.println();
    }
}
